package leetcode.双指针法;

/**
 * 盛最多水的容器
 *
 * 容器的盛水量取决于容器的底和容器较短的那条高
 * 可见 只有较短边会对盛水量造成影响，因此移动较短边的指针，
 *      并比较当前盛水量和当前最大盛水量。直至左右指针相遇。
 *
 * 设有左指针 left和右指针 right，且 left指向的值小于 right的值
 *      容器高度较大的一侧的移动只会造成容器盛水量减小
 *      所以应当移动高度较小一侧的指针，并继续遍历，直至两指针相遇。
 */
public class Test11盛最多水的容器 {

    public static int maxArea(int[] height) {
        int maxArea = 0;
        for (int i = 0; i < height.length; i++)
            for (int j = i + 1; j < height.length; j++)
                maxArea = Math.max(maxArea, Math.min(height[i], height[j]) * (j - i));
        return maxArea;
    }

    public static void main(String[] args) {
        int[] a = new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println(maxArea2(a));
    }

    public static int maxArea2(int[] height) {
        // 设定左右两个指针，且 left < right
        int left = 0;
        int right = height.length - 1;
        int max = 0;
        while (left < right) {
            // 根据两边距离和最短边高度得到面积
            max = Math.max(max, Math.min( height[left], height[right] ) * (right - left));
            // 应当移动高度较小一侧的指针
            // 每次都舍弃最短的并向中心移动一位
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return max;
    }
}
